public class test1 {
    //力扣 LCR 090 打家劫舍II
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));

    }
    public int rob1(int[] nums,int left,int right){
        //只有两个或者一个根本偷不了
        if(left>right) return 0;

        //创建dp表
        //初始化
        //填表
        //返回值
        int n = nums.length;
        int[] dpf = new int[n];
        int[] dpg = new int[n];
        dpf[left] = nums[left];
        for(int i = left;i<=right;i++){
            dpf[i] = dpg[i-1] + nums[i];
            dpg[i] = Math.max(dpf[i-1],dpg[i-1]);
        }
        return Math.max(dpf[right],dpg[right]);
    }
}
